package bintree.map_set.LeetCode;
//219. 存在重复元素 II

import java.util.HashMap;
import java.util.Map;

/**
 * 思路：用Map集合来解决。key存数组元素，vale存对应的索引值
 *  当第一个判断map存在的key时，然后拿出key对应的索引与新元素的索引差是否满足 《 k
 */
public class Num219_containsNearbyDuplicate {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        //遍历数组，存入元素值
        for (int i = 0; i < nums.length; i++) {
                int tmp = nums[i];
                if(map.containsKey(tmp) ){
                    //此时的新元素在key中已经存在
                    //判断新元素索引 i - key中对应的vale索引是否小于等于 k
                    if(i - map.get(tmp) <= k){
                        return true;
                    }
                }
                //如果没遇到就正常的添加元素
            map.put(tmp, i);

        }
        //遍历了都没找到
        return false;
    }
}
